package com.cuz.daileetcode;


import com.cuz.daileetcode.utils.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;

public class Day31 {


    public static int binaryTreeMaxWidth1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //宽度优先遍历队列
        LinkedList<TreeNode> widthHelpQueue = new LinkedList<>();
        //记录节点和 节点属于层的hashMap
        HashMap<TreeNode, Integer> nodeAndLevelMemory = new HashMap<>();
        //初始化 当前根节点 为第一层
        nodeAndLevelMemory.put(root, 1);
        //放到队列末尾
        widthHelpQueue.addLast(root);
        //当前层为
        int curLevel = 1;
        //当前层节点个数 为 0
        int curLevelTreeNodeNum = 0;
        //二叉树最大宽度
        int res = Integer.MIN_VALUE;
        //如果当前队列不为空 代表并没有完全遍历完这个二叉树
        while (!widthHelpQueue.isEmpty()) {
            //拿到队列最前的节点
            TreeNode loopTemp = widthHelpQueue.removeFirst();
            //当前节点所属的层级
            Integer loopNodeLevel = nodeAndLevelMemory.get(loopTemp);
            //如果等于当前层级 说明这一层还没遍历完
            if (loopNodeLevel == curLevel) {
                //数目自增
                curLevelTreeNodeNum++;
            } else {
                //反之说明是新的一层的第一个节点 ，当前层级自增
                curLevel++;
                //结算上一层节点数目
                res = Math.max(curLevelTreeNodeNum, res);
                //当前层节点数目置为1 （不是0因为这个节点是当前层的第一个）
                curLevelTreeNodeNum = 1;
            }
            //记录左节点的层级为当前层+1
            if (loopTemp.left != null) {
                widthHelpQueue.addLast(loopTemp.left);
                nodeAndLevelMemory.put(loopTemp.left, curLevel + 1);
            }
            //记录右节点的层级为当前层+1
            if (loopTemp.right != null) {
                widthHelpQueue.addLast(loopTemp.right);
                nodeAndLevelMemory.put(loopTemp.right, curLevel + 1);
            }
            //最后删除这个节点在map中的数据 可以减少hashMap空间占用
            //这个节点所属层级到此已经没用了
            //nodeAndLevelMemory.remove(loopTemp);
        }
        //最后还需要取curLevelTreeNodeNum 和res中大者
        //因为最后一层所有节点遍历完的时候 队列为空 无法再次进入循环 刷新res
        return Math.max(curLevelTreeNodeNum, res);
    }


    public static int binaryTreeMaxWidth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //宽度优先遍历队列
        LinkedList<TreeNode> widthHelpQueue = new LinkedList<>();
        widthHelpQueue.addLast(root);
        //当前层最后一个节点
        TreeNode curLevelLastNode = root;
        //下一层的最后一个节点
        TreeNode nextLevelLastNode = null;
        //当前层节点个数
        int curLevelTreeNodeNum = 0;
        //二叉树最大宽度
        int res = Integer.MIN_VALUE;
        //如果当前队列不为空 代表并没有完全遍历完这个二叉树
        while (!widthHelpQueue.isEmpty()) {
            //拿到当前节点
            TreeNode curNode = widthHelpQueue.removeFirst();
            //不断的刷新下一层最后一个节点.下一层节点为当前节点的左or 右
            if (curNode.left != null) {
                widthHelpQueue.addLast(curNode.left);
                nextLevelLastNode = curNode.left;
            }
            if (curNode.right != null) {
                widthHelpQueue.addLast(curNode.right);
                nextLevelLastNode = curNode.right;
            }
            //如果当前节点不是这一层最后一个节点
            if (curLevelLastNode != curNode) {
                //这一层节点数目自增
                curLevelTreeNodeNum++;
            } else {
                //否则 res 取curLevelTreeNodeNum+1, res较大者
                //因为是这层最后一个节点 curLevelTreeNodeNum需要加1，
                //不能漏掉这最后一个
                res = Math.max(curLevelTreeNodeNum + 1, res);
                //这一层节点个数置为0 因为要进入下一层了
                curLevelTreeNodeNum = 0;
                //更新当前最后节点为下一层最后一个节点
                curLevelLastNode = nextLevelLastNode;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        root.val = 1;
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        root.left = node2;
        root.right = node3;
        node2.right = node4;
//        node4.left = node5;
//        node4.right = node6;
        System.out.println(binaryTreeMaxWidth1(root));
        System.out.println(binaryTreeMaxWidth2(root));
    }
}
